module AutoBase
  class Graph
    Vertex = Struct.new(:name, :neighbours, :dist, :prev)
    Edge = Struct.new(:v1, :v2, :distance)
    class Edge
      def vertices; [v1, v2]; end
    end

    def initialize(graph)
      @vertices = {}
      @edges = []
      graph.each do |(v1, v2)|
        @vertices[v1] = Vertex.new(v1, []) unless @vertices.has_key?(v1)
        vert1 = @vertices[v1]
        @vertices[v2] = Vertex.new(v2, []) unless @vertices.has_key?(v2)
        vert2 = @vertices[v2]
        vert1.neighbours << vert2
        vert2.neighbours << vert1
        @edges << Edge.new(vert1, vert2, 1)
      end
      @dijkstra_source = nil
    end
    attr_reader :vertices, :edges

    def edge(u, v)
      @edges.find {|e| e.vertices == [u, v] or e.vertices == [v, u]}
    end

    def dijkstra(source)
      q = vertices.values
      q.each {|v| v.dist = 1.0/0.0}
      source.dist = 0
      until q.empty?
        u = q.sort_by {|vertex| vertex.dist}.first
        break if u == 1.0/0.0
        q.delete(u)
        u.neighbours.each do |v|
          if q.include?(v)
            alt = u.dist + edge(u,v).distance
            if alt < v.dist
              v.dist = alt
              v.prev = u
            end
          end
        end
      end
      @dijkstra_source = source
    end

    def shortest_path(source, target)
      dijkstra(source) unless @dijkstra_source == source
      path = []
      u = target
      until u.nil?
        path.unshift(u)
        u = u.prev
      end
      path
    end

    def to_s
      "#<%s vertices=%s edges=%s>" % [self.class.name, vertices.values.inspect, edges.inspect]
    end
  end
end

if __FILE__ == $0
  g = Graph.new([ [:a, :b, 7],
      [:a, :c, 9],
      [:b, :c, 10],
      [:b, :d, 15],
      [:c, :d, 11],
      [:d, :e, 6],
      [:a, :f, 14],
      [:c, :f, 2],
      [:e, :f, 9],
    ])

  start = g.vertices[:a]
  stop  = g.vertices[:e]
  path = g.shortest_path(start, stop)
  puts "shortest path from #{start.name} to #{stop.name} has cost #{stop.dist}:"
  puts path.map {|vertex| vertex.name}.join(" -> ")
end